package slideWindow;

/**
 * @author pengfei.hpf
 * @date 2020/3/10
 * @verdion 1.0.0
 * 567. 字符串的排列
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *
 * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *
 * 示例1:
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 *
 * 示例2:
 *
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 *
 *
 * 注意：
 *
 * 输入的字符串只包含小写字母
 * 两个字符串的长度都在 [1, 10,000] 之间
 */
public class CheckInclusion {
    public boolean checkInclusion(String s1, String s2) {
        if(s1 != null && s2 == null){
            return false;
        }
        if(s1 == null || s2 == null){
            return true;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int match = 0;
        int needSize = 0;
        int[] win = new int[26];
        int[] need = new int[26];
        for(char c: chars1){
            need[c - 'a'] ++;
            if(need[c-'a'] == 1){
                needSize ++;
            }
        }
        int left = 0;
        int right = 0;
        while(right < chars2.length){
            int c = chars2[right] - 'a';
            if(need[c] > 0){
                //TODO: 注意!!! 只有满足条件的才加入到窗口计数
                win[c] ++;
                if(need[c] == win[c]){
                    match ++;
                }
            }
            right ++;
            while(match == needSize){
                if(right - left == chars1.length){
                    return true;
                }
                int c2 = chars2[left] - 'a';
                win[c2] --;
                if(need[c2] > 0 && need[c2] > win[c2]){
                    match --;
                }
                left ++;
            }
        }
        return false;
    }
}
